#class topo is used to route
class topo:
    def __init__(self):
        self.quantity = 0
        self.matrix = {}
        self.distance = {}
    def load(self, topology):
        topoloader = open(topology, 'r')
        topolines = topoloader.readlines()
        for topoline in topolines:
            tricell = topoline.split()
            if len(tricell) == 1:
                self.quantity = int(tricell[0])
            if len(tricell) == 3:
                self.matrix[(int(tricell[0]), int(tricell[1]))] = float(tricell[2])
                self.matrix[(int(tricell[1]), int(tricell[0]))] = float(tricell[2])
        #print 'Topology loaded'
        topoloader.close()
    def floyd_warshall(self):
        for key, distance in self.matrix.items():
            self.distance[key] = distance
        k = 0
        while k < self.quantity:
            i = 0
            while i < self.quantity:
                j = 0
                if self.distance.has_key((i, k)):
                    ref = self.distance[(i, k)]
                else:
                    i = i + 1
                    continue
                while j < self.quantity:
                    if i == j:
                        j = j + 1
                        continue
                    if self.distance.has_key((k, j)):
                        subref = self.distance[(k, j)]
                        if self.distance.has_key((i, j)):
                            if ref + subref < self.distance[(i, j)]:
                                self.distance[(i, j)] = ref + subref
                        else:
                            self.distance[(i, j)] = ref + subref
                    j = j + 1
                i = i + 1
            k = k + 1
    def output(self):
        print '----------Distance----------'
        for k, dis in self.distance.items():
            print k,
            print '=' + str(dis)
        print